A binary translator analyzes blocks of guest code, generates functionally equivalent code blocks (sometimes referred to herein as “code translations,” which result in translated code blocks) for a host machine instruction set architecture, performs optimizations on the code translations and schedules the translated code blocks for execution on the host machine. When successful, the results of executing the code translations on the host machine are the same as the results when executing the guest code on a guest instruction set architecture machine.